googologywikiaorg-20200223-history
User blog:Deedlit11/Results and solutions for the Second Googological Olympiad
Okay, the Second Googological Olympiad has officially ended. Four people sent in solutions, and two sent in solutions to all six problems. The winner is Wojowu, who scored a stellar 47 out of 50 points. On April 15, a person named January First-of-May sent in solutions; while technically his scores should not count, I don't see a problem with adding his scores to the list. Results of the Second Olympiad Name P 1 P 2 P 3 P 4 P 5 Bonus Total Wojowu 5 5 10 10 10 7 47 Wythagoras 5 5 5 9 6 1 31 Cloudy176 5 5 10 January First-of-May 5 5 10 cookiefonster 5 5 Thanks to everyone who participated! I had a lot of fun writing and overseeing the contest. Solution to Problem #1: The answer is \(\prod_{i=0}^{n-1} 103i\), where we take \(1030\) to be \(10\). In fact \(103n = 10^{\prod_{i=0}^{n-1} 103i}\), which we can prove this by induction. Base case: \(1031 = 10^{10} = 10^{1030}\). Inductive step: Assume \(103n = 10^{\prod_{i=0}^{n-1} 103i}\). Then \(103(n+1) = (103n)^{103n} = (10^{\prod_{i=0}^{n-1} 103i})^{103n} = 10^{(\prod_{i=0}^{n-1} 103i) 103n} = 10^{\prod_{i=0}^n 103i}\). Solution to Problem #2: We use the following inequalities for the pth prime \(p_n\): \(n (\log n + \log (\log n) - 1) < p_n < n (\log n + \log (\log n))\) for \(n \ge 6\). So if we let \(N\) be the googolplexth prime, \(N > 10^{10^{100}}(\log(10^{10^{100}}) + \log(\log(10^{10^{100}})) - 1) > 10^{10^{100}}(\log(10^{10^{100}}) + 100 - 1)\\ > 10^{10^{100}}10^{100}\log 10 > 10^{10^{100}}10^{100}(2.302585092994)\) \(N < 10^{10^{100}}(\log(10^{10^{100}}) + \log(\log(10^{10^{100}}))) < 10^{10^{100}}(\log(10^{10^{100}}) + \log(10^{101}))\\ < 10^{10^{100}}(10^{100}\log(10) + 300) < 10^{10^{100}}10^{100}(2.302585092995 + .000000000001)\) Since multiplying a number by \(10^{10^{100}}10^{100}\) does not change its digits, the first 10 digits of \(N\) are \(2302585092\). Solution to Problem #3: Lower bound: Since the function \(x \log x\) is convex (one can check that the second derivative is \(\frac{1}{x}\), which is positive for \(x > 0\)), the integral from \(1\) to \(n\) will be less than its approximation using the trapezoidal rule, so we have \(\int_1^n x \log x \, dx < \sum_{i=1}^{n-1} \frac{i \log i + (i+1)\log(i+1)}{2}\) Therefore \(\log H(n) = \sum_{i=1}^n i \log i > \sum_{i=1}^n i \log i - \sum_{i=1}^{n-1} \frac{i \log i + (i+1)\log(i+1)}{2} + \int_1^n x \log x \, dx\\ = \sum_{i=1}^n i \log i - (\sum_{i=1}^{n-1} i \log i + \frac{n \log n}{2}) + (\frac{x^2 \log x}{2} - \frac{x^2}{4})_{x=1}^n\\ = \frac{n \log n}{2} + \frac{n^2 \log n}{2} - \frac{n^2}{4} + \frac{1}{4}\) \(H(n) > e^{\frac{n^2 \log n + n \log n}{2} - \frac{n^2-1}{4}} = \frac{n^{\frac{n^2+n}{2}}}{e^{\frac{n^2-1}{4}}}\). Upper bound: We can write \(H(n) = (1 - \frac{1}{2})^1 (1 - \frac{1}{3})^3 \ldots (1 - \frac{1}{n})^{\frac{n(n-1)}{2}} n^{\frac{n(n+1)}{2}}\) which we can verify by induction. Base case: \(H(1) = 1\) Inductive step: Assume \(H(n) = (\prod_{i=2}^n (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) n^{\frac{n(n+1)}{2}}\). \(H(n+1) = H(n)(n+1)^{n+1} = (\prod_{i=2}^n (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) n^{\frac{n(n+1)}{2}} (n+1)^{n+1}\\ = (\prod_{i=2}^n (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) (1 - \frac{1}{n+1})^{\frac{n(n+1)}{2}} (n+1)^{\frac{n(n+1)}{2}} (n+1)^{n+1}\\ = (\prod_{i=2}^{n+1} (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) (n+1)^{\frac{(n+1)(n+2)}{2}}\). We use the inequality \((1 - \frac{1}{i})^i < \frac{1}{e}\)*. Then \(H(n) = (\prod_{i=2}^n (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) n^{\frac{n(n+1)}{2}} \\ < (\prod_{i=2}^n e^{-\frac{i-1}{2}})n^{\frac{n(n+1)}{2}} = e^{-\frac{n^2-n}{2}}n^{\frac{n(n+1)}{2}} = \frac{n^{\frac{n(n+1)}{2}}}{e^{\frac{n^2-n}{2}}}\) *to verify the inequality \((1 - \frac{1}{i})^i < \frac{1}{e}\), observe that \(\lim_{i \to \infty} (1 - \frac{1}{i})^i = \frac{1}{e}\), and then observe that \((1 - \frac{1}{i})^i\) is increasing (the first derivative is positive). Category:Blog posts